package com.example.leetcode.prcatice;

import java.util.HashSet;
import java.util.Set;

/**
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 *
 * <p>
 *
 * <p>你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
 *
 * <p>
 *
 * <p>示例:
 *
 * <p>输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"]
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
 */
public class Test38 {

    Set<String> set = new HashSet<>();
    boolean[] b = new boolean[10];

    public String[] permutation(String s) {
        char[] chars = s.toCharArray(); // 转换成字节数组
        dfs(chars,0,"");
        String[] rel = new String[set.size()];
        int i = 0;
        for (String s1:set){
            rel[i] = s1;
            i++;
        }
        return rel;
    }

    void dfs(char[] ch, int u ,String str){
        int length = ch.length;
        if(u == length){
            set.add(str);
            return;
        }
        for (int i = 0;i<length;i++){
            if(!b[i]){
                b[i] = true;
                dfs(ch,u+1,str + ch[i]);   //回溯，逐层返回
                b[i] = false;
            }
        }
    }
}

class Demo38{
  public static void main(String[] args) {
    Test38 t = new Test38();
      String[] abcs = t.permutation("abbc");
      for (String s :abcs ) {
          System.out.println(s);
      }

  }
}